/**
 * @Author: wangliuyang
 * @Date: 2021/8/16 14:28
 * @Description:
 */
public class Solution_674 {

    public int countSubstrings(String s) {
        boolean[][] db = generatePalindromeDB(s);
        int ans = 0;
        for (int i = 0; i < db.length; i++) {
            for (int j = i; j < db[0].length; j++) {
                if (db[i][j]){
                    ans++;
                }
            }
        }
        return ans;
    }
    public boolean[][] generatePalindromeDB(String s){
        int N = s.length();
        boolean[][] db = new boolean[N][N];//数组含义，i-j索引间字符串是否为回文
        for (int i = 0; i < db.length; i++) {
            db[i][i] = true;
        }
        for (int i = 0; i < db.length - 1; i++) {
            db[i][i+1] = s.charAt(i) == s.charAt(i+1);
        }
        for (int i = N - 3; i>=0; i--){
            for (int j = i + 2;j<N; j++){
                db[i][j] = s.charAt(i) == s.charAt(j) ? db[i+1][j-1] : false;
            }
        }
        return db;
    }
}
